package swardToOffer.method_2_sort_or_find.find;

import swardToOffer.struct_4_tree.TreeNode;

/**
 * @Author ChanZany
 * @Date 2021/5/26 9:41
 * @Version 1.0
 * 面试题54：二叉搜索树的第k个结点
 * 题目：给定一棵二叉搜索树，请找出其中的第k大的结点。
 * 方法1:中序遍历(的镜像)k次就可以得到第K大的结点
 * 递归解析：
 * 终止条件： 当节点 root为空（越过叶节点），则直接返回；
 * 递归右子树： 即 dfs(root.right) ；
     * 三项工作：
     * 提前返回： 若 k=0 ，代表已找到目标节点，无需继续遍历，因此直接返回；
     * 统计序号： 执行 k=k−1 （即从 k 减至 0 ）；
     * 记录结果： 若 k=0 ，代表当前节点为第k大的节点，因此记录 res = root.val ；
 * 递归左子树： 即 dfs(root.left) ；
 */
public class KthNodeInBST {
    int res, k;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }

    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.right); // 右
        if (k == 0) return;
        if (--k == 0) res = root.val; //根
        dfs(root.left); // 左
    }


}
